#pragma once
#include <iostream>
#include <assert.h>
#include <time.h>
using namespace std;


template<class T1, class T2>
struct AVLTreeNode
{
	pair<T1,T2> _data;
	struct AVLTreeNode<T1,T2>* _left;
	struct AVLTreeNode<T1, T2>* _right;
	struct AVLTreeNode<T1, T2>* _parent;   // 存的是当前节点的父节点
	int bf;                                // balance factor 记录的是当前位置的平衡因子

	AVLTreeNode(const pair<T1,T2>& data)
		:_data(data)
		,_left(nullptr)
		,_right(nullptr)
		,bf(0)
		,_parent(nullptr)
	{}
};

template<class T1, class T2>
class AVLTree
{
	typedef struct AVLTreeNode<T1, T2> Node;
public:
	AVLTree() = default;

	// 拷贝构造 (深拷贝)
	AVLTree(const AVLTree& x)
	{
		_root = _AVLTreeConstruct(x._root);
	}

	bool Insert(const pair<T1, T2>& x)
	{
		// 第一次插入节点
		if (_root == nullptr)
		{
			_root = new Node(x);
			return true;
		}
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_data.first < x.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_data.first > x.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				// 走到else说明搜索二叉树里面有这个值，所以就不用插入
				return false;
			}
		}
		if (parent->_left == cur && parent->_data.first > x.first)  // 确定插入的值在哪边
		{
			parent->_left = new Node(x);
			parent->_left->_parent = parent;
			cur = parent->_left;
		}
		else
		{
			parent->_right = new Node(x);
			parent->_right->_parent = parent;
			cur = parent->_right;
		}
		// 更新 bf 的操作
		while (parent)
		{
			if (parent->_left == cur && (parent->bf == 0 || parent->bf == 1))
			{
				parent->bf--;
			}
			else if (parent->_right == cur && (parent->bf == 0 || parent->bf == -1))
			{
				parent->bf++;
			}
			else  // 走到这块说明平衡因子为 2 或者 -2
			{
				// 旋转
				if (parent->_right == cur && parent->bf == 1 && cur->bf == 1)
				{
					// 左单旋
					RotateL(parent);
				}
				else if (parent->_left == cur && parent->bf == -1 && cur->bf == -1)
				{
					// 右单旋
					RotateR(parent);
				}
				else if (parent->_left == cur && parent->bf == -1 && cur->bf == 1)
				{
					// 先左旋在右旋
					RotateLR(parent);
				}
				else if (parent->_right == cur && parent->bf == 1 && cur->bf == -1)
				{
					// 先右旋在左旋
					RotateRL(parent);
				}
				else
				{
					assert(false);
				}
				break;
			}
			if (parent->bf == 0)               // 当平衡因子更新完等于 0 之后 便不再向上继续调整
				break;
			cur = parent;
			parent = parent->_parent;
		}
		return true;
	}

	Node* Find(const T1& x)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_data.first < x)
			{
				cur = cur->_right;
			}
			else if (cur->_data.first > x)
			{
				cur = cur->_left;
			}
			else
			{
				return cur;
			}
		}

		return nullptr;
	}

	bool erase(const T1& x)
	{
		// 当只有一个根节点是特殊处理
		if (_root->_left == nullptr && _root->_right == nullptr)
		{
			if (_root->_data.first == x)
			{
				delete _root;
				_root = nullptr;
				return true;
			}
			else
				return false;
		}
		// 删除有两种情况
		// 1、删除的节点只有一个或者没有子节点
		// 2、删除的节点有两个节点
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			// 第一种情况
			if (cur->_data.first > x)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_data.first < x)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				// 处理的特殊情况 根节点是需要消除的节点 并且只有一个子节点
				if (cur == _root && cur->_left == nullptr)
				{
					_root = _root->_right;
					delete cur;
					return true;
				}
				if (cur == _root && cur->_right == nullptr)
				{
					_root = _root->_left;
					delete cur;
					return true;
				}
				int flag = 0;
				if (parent->_right == cur && cur->_left == nullptr)
				{
					parent->_right = cur->_right;
					flag = 1;
				}
				if (parent->_left == cur && cur->_left == nullptr)
				{
					parent->_left = cur->_right;
					flag = 1;
				}
				if (parent->_right == cur && cur->_right == nullptr)
				{
					parent->_right = cur->_left;
					flag = 1;
				}
				if (parent->_left == cur && cur->_right == nullptr)
				{
					parent->_left = cur->_left;
					flag = 1;
				}
				if (flag == 1)
				{
					delete cur;
					return true;
				}
				break;
			}
		}
		// 如果是正常情况下退出循环，说明没有找到要删除的数据
		if (cur == nullptr)
			return false;
		// 第二种情况
		// 可以选择在左边找一个最大值，或者在右边找一个最小值来替代删除的元素
		// 这里实现的是从右边找最小的
		Node* pt = nullptr;
		Node* rt = cur->_right;
		if (rt->_left == nullptr)
		{
			// 说明这个rt的节点就是右边最小的节点
			swap(rt->_data, cur->_data);
			cur->_right = rt->_right;
			delete rt;
			return true;
		}
		// 走到这块说明rt不是右边最小的节点
		while (rt->_left)
		{
			pt = rt;
			rt = rt->_left;
		}
		swap(rt->_data, cur->_data);
		delete rt;
		pt->_left = nullptr;
		return true;

	}


	// 查找二叉树的中序遍历刚好是顺序排序
	void InOrder()
	{
		// 中序遍历需要递归来解决，所以这个 _root 不好传 如果直接用_root 的话 _root 就会被改变
		Node* cur = _root;
		_InOrder(cur);
		cout << endl;
	}

	~AVLTree()
	{
		// 后序删除空间  左 右 根
		_AVLTreeDestory(_root);
		_root = nullptr;
	}

	bool IsAVLTree()
	{
		return _IsAVLTree(_root);
	}

	int Size()
	{
		return _size(_root);
	}

	int Height()
	{
		return _Height(_root);
	}

private:

	bool _IsAVLTree(Node* root)
	{
		if (root == nullptr)
			return true;

		int leftHeight = _Height(root->_left);
		int rightHeight = _Height(root->_right);
		int diff = rightHeight - leftHeight;

		if (abs(diff) > 1)
			return false;

		return _IsAVLTree(root->_left) && _IsAVLTree(root->_right);
	}

	int _size(Node* root)
	{
		if (root == nullptr)
			return 0;
		
		return _size(root->_left) + _size(root->_right) + 1;
	}

	int _Height(Node* root)
	{
		if (root == nullptr)
			return 0;

		int leftHeight = _Height(root->_left);
		int rightHeight = _Height(root->_right);

		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;

	}

	void RotateL(Node* parent)
	{
		Node* parent_Parent = parent->_parent;           // 记录此时根节点的父节点 为后面判断是子树还是根做准备
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		                                                 // 左单旋的操作 连接起来节点 并且改变父节点
		parent->_right = subRL;
		if(subRL)
			subRL->_parent = parent;

		subR->_left = parent;
		parent->_parent = subR;

		if (parent_Parent == nullptr)                    // 说明这个节点就为根节点
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else                                             // 说明这个节点只是一个子树的节点
		{
			if (parent_Parent->_left == parent)
				parent_Parent->_left = subR;
			else
				parent_Parent->_right = subR;
			subR->_parent = parent_Parent;
		}

		subR->bf = parent->bf = 0;                       // 改变这些地方的平衡因子
	}

	void RotateR(Node* parent)
	{
		Node* parent_Parent = parent->_parent;
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;

		if(subLR)
			subLR->_parent = parent;

		subL->_right = parent;
		parent->_parent = subL;


		if (parent_Parent == nullptr)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (parent_Parent->_left == parent)
				parent_Parent->_left = subL;
			else
				parent_Parent->_right = subL;
			subL->_parent = parent_Parent;
		}

		subL->bf = parent->bf = 0;
	}

	void RotateLR(Node* parent)
	{
		Node* SubL = parent->_left;
		Node* SubLR = SubL->_right;
		int bf = SubLR->bf;
		RotateL(parent->_left);
		RotateR(parent);

		// 更新平衡因子
		if (bf == 0)                            // 处理 h == 0 的情况
		{
			parent->bf = 0;
			SubL->bf = 0;
		}
		else if (bf == 1)       // 后面的是处理 h > 0 的情况
		{
			parent->bf = 0;
			SubL->bf = -1;
		}
		else if(bf == -1)
		{
			SubL->bf = 0;
			parent->bf = 1;
		}
		else
		{
			assert(false);
		}
		SubLR->bf = 0;
	}

	void RotateRL(Node* parent)
	{
		Node* SubR = parent->_right;
		Node* SubRL = SubR->_left;
		int bf = SubRL->bf;

		RotateR(parent->_right);
		RotateL(parent);

		if (bf == 0)
		{
			SubR->bf = 0;
			SubRL->bf = 0;
			parent->bf = 0;
		}
		else if (bf == 1)
		{
			SubR->bf = 0;
			SubRL->bf = 0;
			parent->bf = -1;
		}
		else if (bf == -1)
		{
			SubR->bf = 1;
			SubRL->bf = 0;
			parent->bf = 0;
		}
		else
		{
			assert(false);
		}

	}

	void _AVLTreeDestory(Node* root)
	{
		if (root == nullptr)
			return;
		_AVLTreeDestory(root->_left);
		_AVLTreeDestory(root->_right);
		delete root;
	}

	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;
		_InOrder(root->_left);
		cout << root->_data.first << ":" << root->_data.second << endl;
		_InOrder(root->_right);
	}


	Node* _AVLTreeConstruct(Node* root)
	{
		if (root == nullptr)
			return nullptr;
		// 这里深拷贝需要用到前序遍历   根 左 右
		Node* newnode = new Node(root->_data);
		newnode->bf = root->bf;
		newnode->_left = _AVLTreeConstruct(root->_left);
		newnode->_right = _AVLTreeConstruct(root->_right);

		return newnode;
	}

private:
	Node* _root = nullptr;
};